package labuladong.动态规划;

public class Demo01 {
    public static void main(String[] args) {
        // 0-1背包问题
        int[] wt = new int[]{2, 1, 3};
        int[] val = new int[]{4, 2, 3};
        System.out.println(solution(4, 3, wt, val));
    }

    public static int solution(int w, int n, int[] wt, int[] val) {
        int[][] dp = new int[n+1][w+1];
        for(int i=1; i<=n; i++) {
            for (int j=1; j<=w; j++) {
                if(j-wt[i-1] < 0) {
                    dp[i][j] = dp[i-1][j];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-wt[i-1]]+val[i-1]);
                }
            }
        }
        return dp[n][w];
    }
}
